◀ Prev · Parts · Full · Next ▶

Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative: f ∗ ∗ ( 00 ) = ( f ∗ ∗ ) ( 00 ) = f ( 00 ) f ∗ ∗ ( 01 ) = ( ∂ ∂ 1 f ∗ ∗ ) ( 00 ) = − − f ( 00 ) + f ( 01 ) f ∗ ∗ ( 10 ) = ( ∂ ∂ 2 f ∗ ∗ ) ( 00 ) = − − f ( 00 ) + f ( 10 ) f ∗ ∗ ( 11 ) = ( ∂ ∂ 1 ∂ ∂ 2 f ∗ ∗ ) ( 00 ) = f ( 00 ) − − f ( 01 ) − − f ( 10 ) + f ( 11 ) {\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}} this generalizes as the Möbius inversion of the partially ordered set of bit vectors: f ∗ ∗ ( m ) = ∑ ∑ a ⊆ ⊆ m ( − − 1 ) | a | + | m | f ( a ) {\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)} where | a | {\displaystyle |a|} denotes the weight of the bit vector a {\displaystyle a} . Taken modulo 2, this is the Boolean Möbius transform, giving the algebraic normal form coefficients: f ^ ^ ( m ) = ⨁ ⨁ a ⊆ ⊆ m f ( a ) {\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)} In both cases, the sum is taken over all bit-vectors a covered by m, i.e. the "one" bits of a form a subset of the one bits of m.

◀ Prev · Parts · Full · Next ▶